package club.xiaojiawei.greedy;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/27/22 11:51 PM
 * @question 134. 加油站
 * @description 在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
 * 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
 * 给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
 */
public class CanCompleteCircuit134 {

    public static void main(String[] args) {
        CanCompleteCircuit134 test = new CanCompleteCircuit134();
        int result = test.canCompleteCircuit(new int[]{1, 2, 3, 4, 5}, new int[]{3, 4, 5, 1, 2});
        System.out.println(result);
    }

    /**
     * 朴素法-超时
     * @param gas
     * @param cost
     * @return
     */
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int length = gas.length;
        int num;
        int count;
        for (int j = 0; j < length; j++) {
            count = length + 1;
            num = 0;
            int i = j;
            while (count != 0){
                count--;
                i = i % length;
                if ((num += gas[i]) < cost[i]){
                    break;
                }else {
                    num -= cost[i];
                }
                i++;
            }
            if (count == 0){
                return j;
            }
        }
        return -1;
    }

    /**
     * 官方-一次遍历
     * 我们首先检查第 0 个加油站，并试图判断能否环绕一周；如果不能，就从第一个无法到达的加油站开始继续检查。
     * <br><img src="https://zergqueen.gitee.io/images/134.png">
     * @param gas
     * @param cost
     * @return
     */
    public int canCompleteCircuit2(int[] gas, int[] cost) {
        int n = gas.length;
        int i = 0;
        while (i < n) {
            int sumOfGas = 0, sumOfCost = 0;
            int cnt = 0;
            while (cnt < n) {
                int j = (i + cnt) % n;
                sumOfGas += gas[j];
                sumOfCost += cost[j];
                if (sumOfCost > sumOfGas) {
                    break;
                }
                cnt++;
            }
            if (cnt == n) {
                return i;
            } else {
                i = i + cnt + 1;
            }
        }
        return -1;
    }

    /**
     * 民间-一次遍历
     * @param gas
     * @param cost
     * @return
     */
    public int canCompleteCircuit3(int[] gas, int[] cost) {
        int sum = 0;
        int n = gas.length;
        for(int i = 0; i < n; i++){
            sum += gas[i] - cost[i];
        }
        if(sum < 0) return -1;
        int start = 0;
        sum = 0;
        for(int i = 0; i < n; i++){
            sum += gas[i] - cost[i];
            if(sum < 0){
                sum = 0;
                start = i + 1;
            }
        }
        return start;
    }
}
